home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 21 / Cream of the Crop 21 (Terry Blount) (October 1996).iso / editor / gsar110.zip / GSARBMG.C < prev    next >
C/C++ Source or Header  |  1996-08-12  |  14KB  |  438 lines
  1. /* gsarbmg.c *************************************** updated: 960812.19:34 TT
  2.  *
  3.  * Subroutines for fast string searching; no regular expressions
  4.  *
  5.  * Adapted from:
  6.  *
  7.  * Boyer/Moore/Gosper-assisted 'egrep' search, with delta0 table as in
  8.  * original paper (CACM, October, 1977).  No delta1 or delta2.  According to
  9.  * experiment (Horspool, Soft. Prac. Exp., 1982), delta2 is of minimal
  10.  * practical value.  However, to improve for worst case input, integrating
  11.  * the improved Galil strategies (Apostolico/Giancarlo, Siam. J. Comput.,
  12.  * February 1986) deserves consideration.
  13.  *
  14.  * James A. Woods
  15.  * NASA Ames Research Center
  16.  *
  17.  * 29 April 1986 Jeff Mogul Stanford
  18.  * Adapted as a set of subroutines for use by a program. No
  19.  * regular-expression support.
  20.  *
  21.  * 12 February 1992 Tormod Tjaberg
  22.  * Used parts of the original routines to implement extremely fast
  23.  * file search & replace mechanisms on ASCII & non ASCII files taking
  24.  * care not to 'chop' up the search pattern.
  25.  *
  26.  * Note:
  27.  * If a file consists of the following bytes: 'abrabra' a search for
  28.  * 'abra' will yield two matches. However if we are to replace 'abra'
  29.  * with 'foobar' only one occurrence will be changed and the output
  30.  * file will contain 'foobarbra'.
  31.  *
  32.  * Copyright (C) 1992-96 Tormod Tjaberg
  33.  * This is free software, distributed under the terms of the
  34.  * GNU General Public License. For details see the file COPYING
  35.  */
  36.  
  37. #include <stdio.h>
  38. #include <string.h>
  39. #include <stdlib.h>
  40. #include <ctype.h>
  41. #include <sys/types.h>
  42. #include "comp_dep.h"
  43. #include "gsar.h"
  44.  
  45. #define LARGE  (BUFSIZ + PAT_BUFSIZ)  /* overshoot purposes */
  46.  
  47. /* Variables needed to perform the BMG search. 
  48.  */
  49. int            BMG_Patlen;                        /* length of pattern */
  50. unsigned char  BMG_Pattern[PAT_BUFSIZ];           /* actual pattern */
  51. int            BMG_Delta0[256];                   /* ascii only */
  52. unsigned char  BMG_Buffer[BUFSIZ + 2];            /* search buffer */
  53. unsigned char  BMG_Cmap[256];
  54.  
  55. /* Input  : pCtrl - pointer to structure containg output and ctrl info
  56.  *          FileOfs - actual offset in file
  57.  *          BufOfs - match offset in search buffer
  58.  *          pStart - pointer to start of the search buffer
  59.  *          pEnd - pointer to end of the search buffer
  60.  *
  61.  * Returns: nothing
  62.  *
  63.  * Displays buffer information (filename, offset, context) according
  64.  * to the flags set in the structure. i.e. be a bit verbose.
  65.  */
  66. void Verbose(OUTPUT_CTRL *pCtrl, unsigned long FileOfs, int BufOfs,
  67.               unsigned char *pStart, unsigned char *pEnd)
  68. {
  69.    unsigned char *pSC;        /* start of context */
  70.    unsigned char *pEC;        /* end of context */
  71.    unsigned char *pLastSC;    /* last start of context */
  72.  
  73.    unsigned long CtxOfs;      /* context offset */
  74.  
  75.    int i;                     /* loop counter */
  76.  
  77.    if (pCtrl->fFileSpec)                /* display file name */
  78.       fprintf(pCtrl->fpMsg, "%s: ", pCtrl->pInputFile);
  79.  
  80.    if (pCtrl->fByteOffset)              /* display byte offset */
  81.       fprintf(pCtrl->fpMsg, "0x%lx%s",
  82.                FileOfs + BufOfs,
  83.                (pCtrl->fTextual) ? ": " : "");
  84.  
  85.    /* Display a textual or a hexadecimal context
  86.     */
  87.    if (pCtrl->fTextual || pCtrl->fHex)
  88.    {
  89.       pSC = pStart + BufOfs - pCtrl->Context / 2 + BMG_Patlen / 2;
  90.       if (pSC < pStart)                /* outside the buffer ? */
  91.          pSC = pStart;
  92.  
  93.       pEC = pSC + pCtrl->Context;
  94.       if (pEC > pEnd)                  /* outside the buffer ? */
  95.       {
  96.          pEC = pEnd;
  97.  
  98.          /* if we have to truncate to pEnd readjust the start
  99.           * of the context if possible.
  100.           */
  101.          if (pEC - pCtrl->Context > pStart)
  102.             pSC = pEC - pCtrl->Context;
  103.       }
  104.  
  105.       /* display a hexadecimal context
  106.        */
  107.       if (pCtrl->fHex)
  108.       {
  109.          fputc('\n', pCtrl->fpMsg);
  110.  
  111.          CtxOfs = FileOfs + (pSC - pStart);
  112.  
  113.          while (pSC != pEC)
  114.          {
  115.             pLastSC = pSC;                /* remember where we started */
  116.  
  117.             fprintf(pCtrl->fpMsg, "0x%08lx: ", CtxOfs); /* hex offset */
  118.  
  119.             for (i = 0; i < 16; i++)        /* display 16 hex digits */
  120.             {
  121.                if (pSC != pEC)
  122.                   fprintf(pCtrl->fpMsg, "%02x ", (unsigned char) * pSC++);
  123.                else
  124.                   fprintf(pCtrl->fpMsg, "   ");
  125.             }
  126.  
  127.             pSC = pLastSC;                             /* start again */
  128.  
  129.             for (i = 0; i < 16; i++)       /* display 16 characters */
  130.             {
  131.                if (pSC != pEC)
  132.                {
  133. #ifdef MSDOS      /* MSDOS can display all characters except CTRL chars */
  134.                   if (!iscntrl((int) * pSC))
  135. #else             /* its __UNIX__ */
  136.                   if (isprint((int) * pSC))
  137. #endif
  138.                      fputc(*pSC, pCtrl->fpMsg);
  139.                   else
  140.                      fputc('.', pCtrl->fpMsg);
  141.  
  142.                   pSC++;
  143.                }
  144.             }
  145.             CtxOfs += 16;             /* increment context offset by 16 */
  146.             fputc('\n', pCtrl->fpMsg);
  147.          }
  148.  
  149.       }
  150.  
  151.       /* display textual context...
  152.        */
  153.       if (pCtrl->fTextual)
  154.       {
  155.          while (pSC != pEC)
  156.          {
  157. #ifdef MSDOS   /* MSDOS can display all characters except CTRL chars */
  158.             if (!iscntrl((int) * pSC))
  159. #else          /* its __UNIX__ */
  160.             if (isprint((int) * pSC))
  161. #endif
  162.                fputc(*pSC, pCtrl->fpMsg);
  163.             else
  164.                fputc('.', pCtrl->fpMsg);
  165.  
  166.             pSC++;
  167.          }
  168.       }
  169.    }
  170.  
  171.    if (!pCtrl->fHex)
  172.       fputc('\n', pCtrl->fpMsg);
  173. }
  174.  
  175.  
  176. /* Input    : pCtrl - pointer to structure containg output and ctrl info
  177.  * Returns  : number of matches found in file
  178.  *
  179.  * The pattern to search for must already have been set up using BMG_Setup
  180.  *
  181.  * Works by applying the BMG algorithm to a buffer. To ensure the pattern 
  182.  * is not inadvertently chopped up, BMG_Patlen - 1 bytes is always moved 
  183.  * to the start of the buffer. The next time we fill the buffer we fill it
  184.  * with BUFSIZ - (BMG_Patlen - 1) bytes.
  185.  */
  186. long BMG_Search(OUTPUT_CTRL *pCtrl)
  187. {
  188.    register unsigned char *k;
  189.    register unsigned char *s;
  190.    register unsigned char *strend;
  191.  
  192.    register int j;
  193.  
  194.    int  nTrans = 0;   /* number of bytes to transfer to the start of the buffer */
  195.    int  BufOfs;       /* buffer offset for each match */
  196.    int  Cnt = BUFSIZ;
  197.  
  198.    long nMatches = 0;                  /* number of matches found */
  199.    long nBytes;                        /* number of bytes read */
  200.    unsigned long FileOfs = 0;          /* current file offset */
  201.  
  202.    for (;;)
  203.    {
  204.       nBytes = fread(&BMG_Buffer[nTrans], 1, (size_t) Cnt, pCtrl->fpIn);
  205.  
  206.       if (!nBytes)
  207.          break;
  208.  
  209.       s = BMG_Buffer;
  210.  
  211.       strend = s + nBytes + nTrans;
  212.  
  213.       k = BMG_Buffer + BMG_Patlen - 1;
  214.  
  215.       for (;;)
  216.       {
  217.          while ((k += BMG_Delta0[ *(unsigned char *) k]) < strend)
  218.             ;
  219.  
  220.          if (k < (BMG_Buffer + LARGE))
  221.             break;
  222.          k -= LARGE;
  223.  
  224.          j = BMG_Patlen - 1;
  225.          s = k - 1;
  226.  
  227.          while (BMG_Cmap[ *s--] == BMG_Pattern[--j])
  228.             ;
  229.          if (j >= 0)
  230.             k++;
  231.          else
  232.          {
  233.             if (k >= strend)
  234.                break;
  235.  
  236.             /* found submatch, k is on the last letter in the match */
  237.             BufOfs = k - BMG_Buffer + 1 - BMG_Patlen;
  238.  
  239.             nMatches++;
  240.             if (pCtrl->fVerbose)
  241.                Verbose(pCtrl, FileOfs, BufOfs, BMG_Buffer, strend);
  242.  
  243.             k++;
  244.          }
  245.       }
  246.  
  247.       nTrans = BMG_Patlen - 1;
  248.  
  249.       memcpy(BMG_Buffer, strend - nTrans, nTrans); /* move remaining bytes to the start */
  250.       Cnt = BUFSIZ - nTrans;
  251.       FileOfs += Cnt;                              /* calculate file offset  */
  252.    }
  253.  
  254.    return nMatches;
  255. }
  256.  
  257.  
  258. /* Input    : pCtrl - pointer to structure containg output and ctrl info
  259.  *            ReplaceBuf - pointer to buffer which contains replacement
  260.  *            nReplace - numbe